We determine the asymptotic behavior of the maximum subgraph density of largerandom graphs with a prescribed degree sequence. The result applies inparticular to the Erd\H{o}s-R\'{e}nyi model, where it settles a conjecture ofHajek [IEEE Trans. Inform. Theory 36 (1990) 1398-1414]. Our proof consists inextending the notion of balanced loads from finite graphs to their local weaklimits, using unimodularity. This is a new illustration of the objective methoddescribed by Aldous and Steele [In Probability on Discrete Structures (2004)1-72 Springer].
展开▼
机译:我们用规定的度数序列确定更大随机图的最大子图密度的渐近行为。该结果尤其适用于Erd \ H {o} s-R \'{e} nyi模型,在该模型中,可以解决哈杰克[IEEE Trans。通知。理论36(1990)1398-1414]。我们的证明包括使用单模量将平衡载荷的概念从有限图扩展到其局部弱极限。这是Aldous和Steele所描述的客观方法的新例证[In Probability on Discrete Structures(2004)1-72 Springer]。
展开▼